/*
** varset.hh
** Login : <David@sandrock.lrde.epita.fr>
** Started on  Mon Apr  7 13:41:53 2003 David Lesage
** $Id: varset.hh 52 2003-05-19 08:14:55Z burrus_n $
** 
** Copyright (C) 2003 David Lesage
** This program is free software; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 2 of the License, or
** (at your option) any later version.
** 
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
** 
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/

#ifndef   	VARSET_HH_
# define   	VARSET_HH_

# include <iostream>
# include <list>
# include <vector>
# include <cassert>

# include <boost/dynamic_bitset.hpp>

# include "common.hh"
# include "initializer.hh"
# include "var.hh"

namespace evz
{

  /*----------.
  | VarSet<T> |
  `----------*/

  //! Represent a domain of variable, that is, a set of variable.
  /*!  
    The VacFactory given at the initialization MUST not change
    later. Indeed, VarSet relies on the initial total number of
    variable to represent the set, using a bitset.
  */

  template <class T>
  class VarSet
  {
  private:
    typedef Initializer<const Var<T>*> initializer_type;

  public:
    VarSet(const VarSet<T>& vset)
      : vf_(vset.vf_), vars_(vset.vars_), 
	nb_total_configs_(vset.nb_total_configs_), nb_vars_(vset.nb_vars_)
    {}

    VarSet& operator=(const VarSet<T>& vset)
    {
      // FIXME: this operator cannot assign the varfactory, so it must
      // be the same ones.
      assert (vf_ == vset.vf_);
      vars_ = vset.vars_;
      nb_total_configs_ = vset.nb_total_configs_;
      nb_vars_ = vset.nb_vars_;
      return *this;
    }
    
    VarSet(VarFactory<T>& vf)
      : vf_(vf), vars_(vf.size()), nb_total_configs_(1), nb_vars_(0)
    {}

    VarSet(VarFactory<T>& vf, const std::list<Var<T>*>& varlist)
      : vf_(vf), vars_(vf.size()), nb_total_configs_(1), nb_vars_(0)
    {
      for (typename std::list<Var<T>*>::const_iterator var = varlist.begin(); 
	   var != varlist.end();
	   ++var)
	add_var(*(*var));
    }

    VarSet(VarFactory<T>& vf, const initializer_type& varlist)
      : vf_(vf), vars_(vf.size()), nb_total_configs_(1), nb_vars_(0)
    {
      for (typename initializer_type::const_iterator var = varlist.begin(); 
	   var != varlist.end();
	   ++var)
	add_var(*(*var));
    }

    static initializer_type start()
    {
      return initializer_type();
    }

    // Return the maximal number of variables. This is NOT the actual
    // number of variables defined in the set.
    unsigned size() const
    {     
      return vars_.size();
    }

    // Return the number of vars included in the set.
    unsigned get_nb_vars() const
    {     
      return nb_vars_;
    }

    // Add a new var in the varset.
    void add_var(const Var<T>& v)
    {
      assert(v.get_rank() < size());

      vars_[v.get_rank()] = 1;
      nb_total_configs_ *= v.size();
      ++nb_vars_;
    }

    // Remove a var from the varset.
    void del_var(const Var<T>& v)
    {
      assert(v.get_rank() < size());

      if (vars_[v.get_rank()])
	{
	  vars_[v.get_rank()] = 0;
	  nb_total_configs_ /= v.size();
	  --nb_vars_;
	}
    }

    // Return the nth variable included in the varset. This does NOT
    // means the variable of rank n.
    const Var<T>& get_nth_var(unsigned n) const
    {
      assert(n < size());
 
      unsigned cpt = 0; // current var num
      unsigned cpt2 = 0; // current var rank

      for (; cpt2 < vars_.size(); ++cpt2)
	if (vars_[cpt2])
	  {
	    if (cpt == n)
	      break;
	    ++cpt;
	  }

      assert(cpt2 < vars_.size());
      
      return vf_.get_var(cpt2);
    }

    // Return the Var instance associated to a Var rank. This is a
    // proxy to the VarFactory.
    const Var<T>& get_var(unsigned rank) const
    {
      return vf_.get_var(rank);
    }
   
    // Return true if the variable of the specified rank is in the
    // set.
    bool has_var(unsigned rank) const
    {
      return vars_[rank];
    }

    // Return true if the variable v is in the set.
    bool has_var(const Var<T>& v) const
    {
      return has_var(v.get_rank());
    }

    // Return the number of possible configurations between Var of
    // rank r1 and Var of rank r2 (included).
    unsigned get_nb_configs(unsigned r1, unsigned r2) const
    {
      unsigned res = 1;

      for (unsigned cpt = r1; cpt < vars_.size() && cpt <= r2; ++cpt)
	{
	  if (vars_[cpt])
	    {
	      res *= vf_.get_var(cpt).size();
	    }
	}
      return res;
    }

    // Return the total number of configuration.
    unsigned get_nb_configs(void) const
    {
      return nb_total_configs_;
    }

    // Return the highest Variable rank included in the set.
    unsigned get_max_rank(void) const
    {
      unsigned res = 0;

      for (unsigned cpt = 0; cpt < vars_.size(); ++cpt)
	if (vars_[cpt])
	  {
	    unsigned rank = vf_.get_var(cpt).get_rank();
	    if (rank > res)
	      res = rank;
	  }
      return res;
    }

    // Return the intersection with another VarSet.
    VarSet<T> operator&(const VarSet<T>& s) const
    {
      assert (vf_ == s.vf_);
      return VarSet<T>(vf_, vars_ & s.vars_);
    }

    // Intersects the varset with another.
    VarSet<T>& operator&=(const VarSet<T>& s)
    {
      assert (vf_ == s.vf_);
      vars_ &= s.vars_;
      return *this;
    }

    // Return the union with another VarSet.
    VarSet<T> operator|(const VarSet<T>& s) const
    {
      assert (vf_ == s.vf_);
      return VarSet<T>(vf_, vars_ | s.vars_);
    }
   
    // Make the union with another VarSet.
    VarSet<T>& operator|=(const VarSet& s) 
    {
      assert (vf_ == s.vf_);
      vars_ |= s.vars_;
      return *this;
    }
 
    bool operator==(const VarSet<T>& v) const
    { 
      return vars_ == v.vars_;
    }

    bool operator!=(const VarSet<T>& v) const
    { 
      return !(*this == v);
    }

    bool is_subset_of(const VarSet<T>& v) const
    {
      return vars_.is_subset_of(v.vars_);
    }

  private:
    VarSet(VarFactory<T>& vf, const bitset& vars)
      : vf_(vf), vars_(vars), nb_total_configs_(1), nb_vars_(0)
    {
      for (unsigned rank = 0; rank < vars_.size(); rank++)
	if (vars_[rank])
	  {
	    ++nb_vars_;
	    nb_total_configs_ *= vf_.get_var(rank).size();
	  }
    }
    
    VarFactory<T> &vf_;
    bitset vars_;
    unsigned nb_total_configs_;
    unsigned nb_vars_;
  };

  template<class T>
  inline std::ostream&
  operator<<(std::ostream& o, const VarSet<T>& vs)
  {
    o << "{ ";
    unsigned nb_vars = 0;
    for (unsigned cpt = 0; cpt < vs.size(); ++cpt)
	if (vs.has_var(cpt))
	  {
	    o << vs.get_var(cpt);
	    if ( nb_vars < vs.get_nb_vars() - 1 )
	      o << ", ";
	    ++nb_vars;
	  }
    o << " }";
    return o;
  }
  
} // end of evz

#endif	    /* !VARSET_HH_ */
